翻訳と辞書 Words near each other ・ Aprem Natniel ・ Apremilast ・ Apremodo, Ghana ・ Apremont ・ Approximately ・ Approximately finite-dimensional ・ Approximately finite-dimensional C*-algebra ・ Approximately Infinite Universe ・ Approximation ・ Approximation algorithm ・ Approximation error ・ Approximation in algebraic groups ・ Approximation property ・ Approximation theory ・ Approximation to the identity ・ Approximation-preserving reduction ・ Approximations of π ・ Apps (surname) ・ Apps family ・ Apps4Africa ・ Appsbar ・ AppsBuilder ・ AppScale ・ Appscend ・ Appsee ・ AppSense ・ Appserver.io ・ Appsfire ・ AppsFlyer ・ Appsgeyser Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Approximation-preserving reduction ： ウィキペディア英語版 Approximation-preserving reduction In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the distance of solutions from optimal is preserved to some degree. Approximation-preserving reductions are a subset of more general reductions in complexity theory; the difference is that approximation-preserving reductions usually make statements on approximation problems or optimization problems, as opposed to decision problems. Intuitively, problem A is reducible to problem B via an approximation-preserving reduction if, given an instance of problem A and a (possibly approximate) solver for problem B, one can convert the instance of problem A into an instance of problem B, apply the solver for problem B, and recover a solution for problem A that also has some guarantee of approximation. ==Definition== Unlike reductions on decision problems, an approximation-preserving reduction must preserve more than the truth of the problem instances when reducing from one problem to another. It must also maintain some guarantee on the relationship between the cost of the solution to the cost of the optimum in both problems. To formalize: Let $A$ and $B$ be optimization problems. Let $x$ be an instance of problem $A$, with optimal solution $OPT(x)$. Let $c\_A(x,\; y)$ denote the cost of a solution $y$ to an instance $x$ of problem $A$. This is also the metric used to determine which solution is considered optimal. An approximation-preserving reduction is a pair of functions $(f,\; g)$ (which often must be computable in polynomial time), such that: * $f$ maps an ''instance'' $x$ of $A$ to an ''instance'' $x\text{'}$ of $B$. * $g$ maps a ''solution'' $y\text{'}$ of $B$ to a ''solution'' $y$ of $A$. * $g$ preserves some guarantee of the solution's ''performance,'' or ''approximation ratio'', defined as $R\_A(x,\; y)\; =\; \backslash max\; \backslash left\; (\; \backslash frac,\; \backslash frac\; \backslash right\; )$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Approximation-preserving reduction」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.